package acwing.图;


import java.util.Arrays;
import java.util.Scanner;

/**
 * acwing有边数限制的最短路
 *
 * @author yang
 * @date 2022/1/8
 */
public class Bellman_Ford {

    static int n, m, k;
    static int N = 100010;
    static int INF = 0x3f3f3f3f;
    static int[][] egde = new int[N][3];
    static int[] dist = new int[510];
    static int[] backup = new int[510];

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        for (int i = 1; i <= m; i++) {
            egde[i][0] = sc.nextInt(); // 点
            egde[i][1] = sc.nextInt(); // 点
            egde[i][2] = sc.nextInt(); // 权重

        }
        int t = bellman();
        if (t != 0) {
            System.out.println(t);
        } else {
            System.out.println("impossible");
        }
    }

    private static int bellman() {

        Arrays.fill(dist, INF);
        dist[1] = 0;

        for (int i = 0; i < k; i++) {
            backup = Arrays.copyOf(dist, N);
            for (int j = 1; j <= m; j++) {
                int a = egde[j][0];
                int b = egde[j][1];
                int w = egde[j][2];
                dist[b] = Math.min(dist[b], backup[a] + w);
            }
        }
        if (dist[n] >= INF / 2) return 0;
        return dist[n];
    }

}
